

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:周次煜
 * Date: 2024-03-31
 * Time：18:53
 */

package linklist;
public class MyLinkedList extends AbLinkList{


    public static class  LinkedNode {
        public   LinkedNode prev;

        public  int val;
        public LinkedNode next;

        public LinkedNode(int val) {
            this.val = val;
        }
    }



    public LinkedNode head;

    public LinkedNode last;

    @Override
    public void addFirst(int data) {
        LinkedNode node=new LinkedNode(data);
        if (isEmpty()) {
            head=last=node;
            return;
        }
        head.prev=node;
        node.next=head;
        head=node;

    }

    // 尾插数据
    @Override
    public void addLast(int data) {
        LinkedNode node=new LinkedNode(data);
        if (isEmpty()) {
            head=last=node;
            return;
        }

        last.next=node;
        node.prev=last;
        last=node;

    }

    public  void checkIndex(int index) throws IndexOutOfBoundsException{
        if (index<0 || index > size()) {
            throw  new IndexOutOfBoundsException("下标异常！");
        }
    }



    // 增加某位置的数据
    @Override
    public boolean addIndex(int index, int data) {
        try {
            checkIndex(index);
        } catch (IndexOutOfBoundsException e) {
            e.printStackTrace();
            return false;
        }

        if (index==0) {
            addFirst(data);
            return true;
        }

        if (index==size()) {
            addLast(data);
            return true;
        }
        LinkedNode cur=head;
        LinkedNode node=new LinkedNode(data);
        for (int i = 0; i < index; i++) {
            cur=cur.next;
        }


        cur.prev.next=node;
        node.prev=cur.prev;
        cur.prev=node;
        node.next=cur;

        return true;
    }

    // 是否包含 key
    @Override
    public boolean contains(int key) {

        LinkedNode cur=head;
        for (int i = 0; i < size(); i++) {
            if (cur.val==key) {
                return true;
            }
            cur=cur.next;
        }

        return false;
    }

    // 移除一个 key 数据
    @Override
    public boolean remove(int key) {
        if (isEmpty()) {
            return false;
        }

        if (head.val==key) {
//            head.val=null;
            head=head.next;
            head.prev=null;
            return true;
        }

        if (last.val==key) {
//            last.val=null;
            last=last.prev;
            last.next=null;
            return true;
        }

        LinkedNode cur= head;
        while (cur !=null) {
            if (cur.val==key) {
//                cur.val=null;
                cur.prev.next=cur.next;
                cur.next.prev=cur.prev;
                return true;
            }

            cur=cur.next;

        }

        return false;
    }

    // 移除所以 key 的数据
    @Override
    public void removeAllKey(int key) {


        LinkedNode cur= head.next;
        while (cur.next !=null) {
            if (cur.val==key) {
//                cur.val=null;
                cur.prev.next=cur.next;
                cur.next.prev=cur.prev;

            }
                cur=cur.next;


        }

        if (head.val==key) {
//            head.val=null;
            head=head.next;
            head.prev=null;
        }

        if (last.val==key) {
//            last.val=null;
            last=last.prev;
            last.next=null;
        }
    }

    // 双链表长度

    @Override
    public int size() {
        int count=0;
        LinkedNode cur=head;
        while (cur !=null) {
            count++;
            cur=cur.next;
        }

        return  count;
    }

    // 打印双链表
    @Override
    public void display() {
        LinkedNode cur=head;
        System.out.print("null <- ");
        while (cur !=null) {
            System.out.print(cur.val+" -> ");
            cur=cur.next;
        }
        System.out.print("null\n");
    }

    // 释放双链表
    @Override
    public void clear() {
        LinkedNode cur=head;
        while (cur !=null) {
           LinkedNode tmp=cur.next;
//           cur.val=null;
           cur=null;
           cur=tmp;

        }
        head=null;
    }

    // 检查是否为空
    private boolean isEmpty() {
        return  size()==0;
    }

}




